package chapter05_string;

/**
 * 描述：是否为旋转词
 *      aaa2a a2aaa
 *      a2aa aa2a
 * @author hl
 * @date 2021/8/8 11:39
 */
public class IsRotation {
    public static void main(String[] args) {
        IsRotation main = new IsRotation();
        String str1 = "aaa2a";
        String str2 = "a2aaa";
        boolean flag1 = main.isRotation(str1, str2);
        boolean flag2 = main.isRotation2(str1, str2);
        System.out.println(flag1);
        System.out.println(flag2);
        String s1 = "abdfasgadsg";
        String s2 = "asg";
        int index = main.getIndexOf(s1, s2);
        System.out.println(index);
    }

    /**
     * 利用KMP算法达到时间复杂度O(N)
     * @param str1
     * @param str2
     * @return
     */
    public boolean isRotation2(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        str2 += str2;
        return getIndexOf(str2, str1) != -1; //KMP
    }

    public boolean isRotation(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        for (int i = str2.length() - 1; i >= 0; i--) {
            if (str2.charAt(i) == str1.charAt(0) && chekRotation(str1, str2, 0, i)) {
                return true;
            }
        }
        return false;
    }

    private boolean chekRotation(String str1, String str2, int index1, int index2) {
        int n = str1.length();
        for (int i = 0; i < n; i++) {
            index1 = index1 == n ? 0 : index1;
            index2 = index2 == n ? 0 : index2;
            if (str1.charAt(index1++) != str2.charAt(index2++)) {
                return false;
            }
        }
        return true;
    }


    /**
     * KMP  检查s1是否包含s2
     * @param s1
     * @param s2
     * @return
     */
    public int getIndexOf(String s1, String s2){
        if (s1 == null || s2 == null || s1.length() < s2.length()) {
            return -1;
        }
        int[] next = getNextArr(s2);
        int i = 0, j = 0;
        while(i < s1.length() && j < s2.length()){
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            }else if (next[j] == -1) {
                i++;
            }else {
                j = next[j];
            }
        }
        return j == s2.length() ? i - s2.length() : -1;
    }

    /**
     * 求出next数组，next[i]表示0~i-1的字符串相同的前后缀数量
     * @param str
     * @return
     */
    private int[] getNextArr(String str) {
        int[] next = new int[str.length()];
        next[0] = -1;
        next[1] = 0;
        int cn = 0, i = 2;
        while(i < str.length()){
            if (str.charAt(i - 1) == str.charAt(cn)) {
                next[i++] = ++cn;
            }else if (cn > 0) {
                //相同的后缀必定是0~cn的子串，因为cn-1是和i-2匹配的，第二长的以str.charAt(i-2)结尾的公共前缀就是next[cn]
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }
}
